package com.ting.test.algorithms.查找算法.归并查找;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 在一个数组中，
 * 任何一个前面的数a，和任何一个后面的数b，
 * 如果(a,b)是降序的，就称为逆序对
 * 返回数组中所有的逆序对
 * arr=new int[]{2,3,5,2,4,3,8,1,6,4};
 * 比如
 * 对于2  2,1
 * 对于3 3,2  3,1
 * 对于5 ,5,2 5,4 5,3 5,1  5,4是逆序
 * 以此类推
 * <p>
 * 可以发现
 * 如果我们把数组分成左右两个 逆序有序的数组
 * 那么 如果左边的一个元素下标A比右边的某一个元素下标B大 那么左边的元素下标A 一定比B后面的元素都大，则arr[A],arr[B] arr[A],arr[B+1] ,arr[n-bB+1] 都是逆序对
 * 这其实就是归并排序的merage部分
 * <p>
 * <p>
 * <p>
 * 思路
 * <p>
 * {2,3,5,2,4}   {3,8,1,6,4}
 * {5,4,3,2,2}   {8,6,4,3,1}
 * {8,6,5,4,3,3,2,2}
 */
public class 逆序问题 {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 5, 2, 4, 3, 8, 1, 6, 4};
        List<Pair> result = func(arr);
        result.forEach((pair) -> {
            System.out.println("[" + pair.key + "," + pair.value + "]");
        });
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+",");
        }
    }

    private static List<Pair> func(int[] arr) {
        if (arr == null || arr.length == 1) {
            return new ArrayList<>();
        }
        int L = 0;
        int R = arr.length - 1;
        return process(arr, L, R);
    }

    private static List<Pair> process(int[] arr, int L, int R) {
        if (L == R) {
            return new ArrayList<>();
        }
        int M = L + ((R - L) >> 1);

        List<Pair> left = process(arr, L, M);
        List<Pair> right = process(arr, M + 1, R);
        left.addAll(right);
        left.addAll(merge(arr, L, M, R));
        return left;
    }
    private static List<Pair> merge(int[] arr, int L, int M, int R) {
        List<Pair> pairList = new ArrayList<>();
        int[] help = new int[R - L + 1];
        int LIndex = L;
        int RIndex = M+1;
        int index =0;
        while (LIndex <= M && RIndex <= R) {
            if (arr[LIndex] > arr[RIndex]) {
                for(int i=RIndex;i<=R;i++){
                    pairList.add(new Pair(arr[LIndex], arr[i]));
                }
            }
            help[index++] = arr[LIndex] > arr[RIndex] ? arr[LIndex++] : arr[RIndex++];
        }

        while (LIndex <= M) {
            help[index++] = arr[LIndex++];
        }
        while (RIndex <= R) {
            help[index++] = arr[RIndex++];
        }

        for (int i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }

        return pairList;
    }

    static class Pair {
        int key;
        int value;

        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }

}
